#include <proc.h>
#include <kmalloc.h>
#include <string.h>
#include <sync.h>
#include <pmm.h>
#include <error.h>
#include <sched.h>
#include <elf.h>
#include <vmm.h>
#include <trap.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* ------------- process/thread mechanism design&implementation -------------
(an simplified Linux process/thread mechanism )
introduction:
  ucore implements a simple process/thread mechanism. process contains the independent memory sapce, at least one threads
for execution, the kernel data(for management), processor state (for context switch), files(in lab6), etc. ucore needs to
manage all these details efficiently. In ucore, a thread is just a special kind of process(share process's memory).
------------------------------
process state       :     meaning               -- reason
    PROC_UNINIT     :   uninitialized           -- alloc_proc
    PROC_SLEEPING   :   sleeping                -- try_free_pages, do_wait, do_sleep
    PROC_RUNNABLE   :   runnable(maybe running) -- proc_init, wakeup_proc, 
    PROC_ZOMBIE     :   almost dead             -- do_exit

-----------------------------
process state changing:
                                            
  alloc_proc                                 RUNNING
      +                                   +--<----<--+
      +                                   + proc_run +
      V                                   +-->---->--+ 
PROC_UNINIT -- proc_init/wakeup_proc --> PROC_RUNNABLE -- try_free_pages/do_wait/do_sleep --> PROC_SLEEPING --
                                           A      +                                                           +
                                           |      +--- do_exit --> PROC_ZOMBIE                                +
                                           +                                                                  + 
                                           -----------------------wakeup_proc----------------------------------
-----------------------------
process relations
parent:           proc->parent  (proc is children)
children:         proc->cptr    (proc is parent)
older sibling:    proc->optr    (proc is younger sibling)
younger sibling:  proc->yptr    (proc is older sibling)
-----------------------------
related syscall for process:
SYS_exit        : process exit,                           -->do_exit
SYS_fork        : create child process, dup mm            -->do_fork-->wakeup_proc
SYS_wait        : wait process                            -->do_wait
SYS_exec        : after fork, process execute a program   -->load a program and refresh the mm
SYS_clone       : create child thread                     -->do_fork-->wakeup_proc
SYS_yield       : process flag itself need resecheduling, -- proc->need_sched=1, then scheduler will rescheule this process
SYS_sleep       : process sleep                           -->do_sleep 
SYS_kill        : kill process                            -->do_kill-->proc->flags |= PF_EXITING
                                                                 -->wakeup_proc-->do_wait-->do_exit   
SYS_getpid      : get the process's pid

*/

// the process set's list
list_entry_t proc_list;

#define HASH_SHIFT          10
#define HASH_LIST_SIZE      (1 << HASH_SHIFT)
#define pid_hashfn(x)       (hash32(x, HASH_SHIFT))

// has list for process set based on pid
static list_entry_t hash_list[HASH_LIST_SIZE];

// idle proc
struct proc_struct *idleproc = NULL;
// init proc
struct proc_struct *initproc = NULL;
// current proc
struct proc_struct *current = NULL;

static int nr_process = 0;

void kernel_thread_entry(void);
void forkrets(struct trapframe *tf);
void switch_to(struct context *from, struct context *to);

// alloc_proc - alloc a proc_struct and init all fields of proc_struct
static struct proc_struct *
alloc_proc(void) {
    struct proc_struct *proc = kmalloc(sizeof(struct proc_struct));
    if (proc != NULL) {
    //LAB4:EXERCISE1 YOUR CODE
    /*
     * below fields in proc_struct need to be initialized
     *       enum proc_state state;                      // Process state
     *       int pid;                                    // Process ID
     *       int runs;                                   // the running times of Proces
     *       uintptr_t kstack;                           // Process kernel stack
     *       volatile bool need_resched;                 // bool value: need to be rescheduled to release CPU?
     *       struct proc_struct *parent;                 // the parent process
     *       struct mm_struct *mm;                       // Process's memory management field
     *       struct context context;                     // Switch here to run process
     *       struct trapframe *tf;                       // Trap frame for current interrupt
     *       uintptr_t cr3;                              // CR3 register: the base addr of Page Directroy Table(PDT)
     *       uint32_t flags;                             // Process flag
     *       char name[PROC_NAME_LEN + 1];               // Process name
     */
<<<<<<< HEAD
        // proc->cr3=boot_cr3;
        // proc->tf=NULL;
        // proc->state=PROC_UNINIT;
        // proc->pid=-1;
        // proc->runs=0;
        // proc->kstack=0;
        // proc->need_resched=0;
        // proc->parent=NULL;
        // proc->mm=NULL;
        // proc->flags=0;
        // memset(&(proc->context), 0, sizeof(struct context));
        // memset(proc->name, 0, PROC_NAME_LEN);

        proc->state = PROC_UNINIT; // 未初始化状态
        // 分配唯一的进程ID (可以通过全局计数器实现)
        // static int next_pid = 1;
        // proc->pid = next_pid++;
        proc->pid = -1;
        // 初始化运行次数
        proc->runs = 0;
        // 分配内核栈空间，初始化中直接置0
        // proc->kstack = (uintptr_t)kmalloc(KSTACKSIZE);
        proc->kstack = 0;
        // cprintf("=======================================%d\n", proc->kstack);
        // if (proc->kstack == 0)
        // {
        //     kfree(proc);
        //     return NULL; // 内核栈分配失败
        // }
        // 初始化其他字段
        proc->need_resched = 0;                              // 无需重新调度
        proc->parent = NULL;                                 // 无父进程
        proc->mm = NULL;                                     // 无内存管理结构
        memset(&(proc->context), 0, sizeof(struct context)); // 将上下文清零
        proc->tf = NULL;                                     // 暂时不设置trapframe
        proc->cr3 = boot_cr3;                                // 页目录表
        proc->flags = 0;                                     // 无特殊标志
        // 初始化进程名称为空字符串
        memset(proc->name, 0, PROC_NAME_LEN + 1);
=======
        proc->state = PROC_UNINIT;                      //状态为未初始化
        proc->pid = -1;                                 //pid为未赋值
        proc->runs = 0;                                 //运行时间为0
        proc->kstack = 0;                               //除了idleproc其他线程的内核栈都要后续分配
        proc->need_resched = 0;                         //不需要调度切换线程
        proc->parent = NULL;                            //没有父线程
        proc->mm = NULL;                                //未分配内存
        memset(&(proc->context), 0, sizeof(struct context));//将上下文变量全部赋值为0，清空
        proc->tf = NULL;                                //初始化没有中断帧
        proc->cr3 = boot_cr3;                           //内核线程的cr3为boot_cr3，即页目录为内核页目录表
        proc->flags = 0;                                //标志位为0
        memset(proc->name, 0, PROC_NAME_LEN+1);         //将线程名变量全部赋值为0，清空

>>>>>>> 7f96ff6f3433253c4987d4cf95e2e284ecabd53f
    }
    return proc;
}

// set_proc_name - set the name of proc
char *
set_proc_name(struct proc_struct *proc, const char *name) {
    memset(proc->name, 0, sizeof(proc->name));
    return memcpy(proc->name, name, PROC_NAME_LEN);
}

// get_proc_name - get the name of proc
char *
get_proc_name(struct proc_struct *proc) {
    static char name[PROC_NAME_LEN + 1];
    memset(name, 0, sizeof(name));
    return memcpy(name, proc->name, PROC_NAME_LEN);
}

// get_pid - alloc a unique pid for process
static int
get_pid(void) {
    static_assert(MAX_PID > MAX_PROCESS); //在编译期间确保MAX_PID大于MAX_PROCESS
    struct proc_struct *proc; //进程块
    list_entry_t *list = &proc_list, *le; //指向进程列表的指针，处理当前列表项的指针
    static int next_safe = MAX_PID, last_pid = MAX_PID;//全局静态变量next_safe初始值为最大进程数
    if (++ last_pid >= MAX_PID) {
        //last_pid第一次赋值为1
        last_pid = 1;
        goto inside; 
    }
    if (last_pid >= next_safe) {
        //如果last_pid>=next_safe就设置next_safe为MAX_PID
    inside:
        next_safe = MAX_PID;
    repeat:
        //遍历链表，确保last_pid和现有的进程的PID不相等，更新next_safe
        le = list;
        while ((le = list_next(le)) != list) {
            proc = le2proc(le, list_link);
            if (proc->pid == last_pid) { 
                if (++ last_pid >= next_safe) {
                    if (last_pid >= MAX_PID) {
                        last_pid = 1;
                    }
                    next_safe = MAX_PID;
                    goto repeat;
                }
            }
            else if (proc->pid > last_pid && next_safe > proc->pid) {
                next_safe = proc->pid;
            }
        }
    }
    return last_pid;
}

// proc_run - make process "proc" running on cpu
// NOTE: before call switch_to, should load  base addr of "proc"'s new PDT
void proc_run(struct proc_struct *proc)
{
    if (proc != current)
    {
        // LAB4:EXERCISE3 2212603
        /*
<<<<<<< HEAD
         * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
         * MACROs or Functions:
         *   local_intr_save():        Disable interrupts
         *   local_intr_restore():     Enable Interrupts
         *   lcr3():                   Modify the value of CR3 register
         *   switch_to():              Context switching between two processes
         */

        bool intr_flag;             // 中断状态
        local_intr_save(intr_flag); // 禁止中断
        struct proc_struct *tmp = current;
        current = proc;
        lcr3(current->cr3); // CR3寄存器指向页目录表的物理地址
        switch_to(&(tmp->context), &(proc->context));
        local_intr_restore(intr_flag); // 恢复允许中断
=======
        * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
        * MACROs or Functions:
        *   local_intr_save():        Disable interrupts
        *   local_intr_restore():     Enable Interrupts
        *   lcr3():                   Modify the value of CR3 register
        *   switch_to():              Context switching between two processes
        */
        bool intr_flag;
        local_intr_save(intr_flag);
        struct proc_struct * temp = current;
        current = proc;
        lcr3(current->cr3);
        switch_to(&(temp->context),&(proc->context));
        local_intr_restore(intr_flag);

>>>>>>> 7f96ff6f3433253c4987d4cf95e2e284ecabd53f
    }
}

// forkret -- the first kernel entry point of a new thread/process
// NOTE: the addr of forkret is setted in copy_thread function
//       after switch_to, the current proc will execute here.
static void
forkret(void) {
    forkrets(current->tf);
}

// hash_proc - add proc into proc hash_list
static void
hash_proc(struct proc_struct *proc) {
    //将proc结构体节点添加到哈希表
    //pid_hashfn(proc->pid)函数计算出的哈希值来确定存储位置
    //proc->hash_link添加到对应位置的链表
    list_add(hash_list + pid_hashfn(proc->pid), &(proc->hash_link));
}

// find_proc - find proc frome proc hash_list according to pid
struct proc_struct *
find_proc(int pid) {
    if (0 < pid && pid < MAX_PID) {
        list_entry_t *list = hash_list + pid_hashfn(pid), *le = list;
        while ((le = list_next(le)) != list) {
            struct proc_struct *proc = le2proc(le, hash_link);
            if (proc->pid == pid) {
                return proc;
            }
        }
    }
    return NULL;
}

// kernel_thread - create a kernel thread using "fn" function
// NOTE: the contents of temp trapframe tf will be copied to 
//       proc->tf in do_fork-->copy_thread function
int
kernel_thread(int (*fn)(void *), void *arg, uint32_t clone_flags) {
    struct trapframe tf;
    memset(&tf, 0, sizeof(struct trapframe));
    tf.gpr.s0 = (uintptr_t)fn;      //函数入口
    tf.gpr.s1 = (uintptr_t)arg;     //函数参数
    tf.status = (read_csr(sstatus) | SSTATUS_SPP | SSTATUS_SPIE) & ~SSTATUS_SIE;
    tf.epc = (uintptr_t)kernel_thread_entry;    //epc指向kernel_thread_entry，即执行s0指向的函数
    return do_fork(clone_flags | CLONE_VM, 0, &tf);
}

// setup_kstack - alloc pages with size KSTACKPAGE as process kernel stack
static int
setup_kstack(struct proc_struct *proc) { //为进程分配内核栈
//调用alloc_pages函数为内核栈分配大小为KSTACKPAGE的页面
    struct Page *page = alloc_pages(KSTACKPAGE);
    if (page != NULL) {//分配成功
        //将分配到的页面转换为内核虚拟地址
        //表示进程的内核栈其实地址
        proc->kstack = (uintptr_t)page2kva(page);
        return 0;
    }
    return -E_NO_MEM;//没有足够内存可用
}

// put_kstack - free the memory space of process kernel stack
static void
put_kstack(struct proc_struct *proc) {
    //proc->kstack转换为对应的页结构体指针
    //释放对应的页
    free_pages(kva2page((void *)(proc->kstack)), KSTACKPAGE);
}

// copy_mm - process "proc" duplicate OR share process "current"'s mm according clone_flags
//         - if clone_flags & CLONE_VM, then "share" ; else "duplicate"
static int
copy_mm(uint32_t clone_flags, struct proc_struct *proc) {
    assert(current->mm == NULL);
    /* do nothing in this project */
    return 0;
}

// copy_thread - setup the trapframe on the  process's kernel stack top and
//             - setup the kernel entry point and stack of process
//设置进程内核栈和上下文
static void
copy_thread(struct proc_struct *proc, uintptr_t esp, struct trapframe *tf) {
    //内核栈上分配一块空间保存tf
    //tf指向的位置距离栈顶KSTACKSIZE - sizeof(struct trapframe)字节
    proc->tf = (struct trapframe *)(proc->kstack + KSTACKSIZE - sizeof(struct trapframe));
    *(proc->tf) = *tf; //传入的tf内容复制到proc->tf指向的内存

    // Set a0 to 0 so a child process knows it's just forked
    proc->tf->gpr.a0 = 0;  //a0设置为0表示为子进程
    //esp非空则设置tf栈指针为esp,否则指向自己
    //将线程的栈指针设置为指定的地址
    proc->tf->gpr.sp = (esp == 0) ? (uintptr_t)proc->tf : esp;

    //设置上下文信息
    proc->context.ra = (uintptr_t)forkret;//上下文的ra（返回地址）设置为forkret入口
    proc->context.sp = (uintptr_t)(proc->tf);//将tp放置在上下文的栈顶
}

/* do_fork -     parent process for a new child process
 * @clone_flags: used to guide how to clone the child process
 * @stack:       the parent's user stack pointer. if stack==0, It means to fork a kernel thread.
 * @tf:          the trapframe info, which will be copied to child process's proc->tf
 */
int
do_fork(uint32_t clone_flags, uintptr_t stack, struct trapframe *tf) {
    int ret = -E_NO_FREE_PROC;  //没有空闲进程可用
    struct proc_struct *proc;   //创建新的线程

    // 检查当前进程数量是否超过最大进程数量限制
    if (nr_process >= MAX_PROCESS) {
        goto fork_out;//跳转到fork_out
    }

    ret = -E_NO_MEM;//在发生内存分配失败时可以返回适当的错误码
    //LAB4:EXERCISE2 YOUR CODE
    /*
     * Some Useful MACROs, Functions and DEFINEs, you can use them in below implementation.
     * MACROs or Functions:
     *   alloc_proc:   create a proc struct and init fields (lab4:exercise1)
     *   setup_kstack: alloc pages with size KSTACKPAGE as process kernel stack
     *   copy_mm:      process "proc" duplicate OR share process "current"'s mm according clone_flags
     *                 if clone_flags & CLONE_VM, then "share" ; else "duplicate"
     *   copy_thread:  setup the trapframe on the  process's kernel stack top and
     *                 setup the kernel entry point and stack of process
     *   hash_proc:    add proc into proc hash_list
     *   get_pid:      alloc a unique pid for process
     *   wakeup_proc:  set proc->state = PROC_RUNNABLE
     * VARIABLES:
     *   proc_list:    the process set's list
     *   nr_process:   the number of process set
     */

    //    1. call alloc_proc to allocate a proc_struct
    //    2. call setup_kstack to allocate a kernel stack for child process
    //    3. call copy_mm to dup OR share mm according clone_flag
    //    4. call copy_thread to setup tf & context in proc_struct
    //    5. insert proc_struct into hash_list && proc_list
    //    6. call wakeup_proc to make the new child process RUNNABLE
    //    7. set ret vaule using child proc's pid
<<<<<<< HEAD
    proc = alloc_proc();
    if (proc == NULL)
    {
        goto fork_out;
    }
    if(setup_kstack(proc) == -4)
    {
        goto bad_fork_cleanup_kstack;
    }
    proc->parent = current; // ?
    if(copy_mm(clone_flags, proc) != 0)
    {
        goto bad_fork_cleanup_proc;
    }
    copy_thread(proc, stack, tf);
    proc->pid = get_pid();
    hash_proc(proc);
    // list_add(&proc_list,&(proc->list_link));
    proc->list_link.next = proc_list.next;
    proc_list.next = &(proc->list_link);
    proc->list_link.prev = &(proc_list);
    proc->list_link.next->prev = &(proc->list_link);
    nr_process++;
    // proc->state = PROC_RUNNABLE;
    wakeup_proc(proc);  
    ret = proc->pid;
=======

    // 分配一个进程控制块  
    proc = alloc_proc();
    if(proc==NULL)//分配失败
        goto fork_out;  
>>>>>>> 7f96ff6f3433253c4987d4cf95e2e284ecabd53f

    // 设置当前进程为新进程的父进程
    proc->parent = current;

    // 为新进程分配内核栈
    if(setup_kstack(proc))
        goto bad_fork_cleanup_kstack;//跳转进行清理

    // 复制进程的内存布局信息，以确保新进程拥有与原进程相同的内存环境
    if(copy_mm(clone_flags,proc))
        goto bad_fork_cleanup_proc;//失败则进行清理
    
    // 复制原进程的上下文到新进程
    copy_thread(proc, stack, tf);

    //get_pid中的全局变量需要原子性的更改，禁止中断
    bool intr_flag;
    local_intr_save(intr_flag);
    
    // 为新进程分配一个唯一的进程号
    proc->pid = get_pid();

    // 将新进程添加到进程列表，并允许中断
    hash_proc(proc);
    list_add(&proc_list,&(proc->list_link));//将proc->list_link加到proc_list后
    nr_process ++;//更新进程数量计数器
    local_intr_save(intr_flag);

    // 唤醒新进程，进入可调度状态
    wakeup_proc(proc);
    
    // 返回新进程号pid
    ret = proc->pid;

fork_out://结束，返回ret
    return ret;

bad_fork_cleanup_kstack://分配内核栈失败
    put_kstack(proc);//释放内核栈
bad_fork_cleanup_proc://复制内存布局信息失败
    kfree(proc);//释放进程控制
    goto fork_out;
}

// do_exit - called by sys_exit
//   1. call exit_mmap & put_pgdir & mm_destroy to free the almost all memory space of process
//   2. set process' state as PROC_ZOMBIE, then call wakeup_proc(parent) to ask parent reclaim itself.
//   3. call scheduler to switch to other process
int
do_exit(int error_code) {
    panic("process exit!!.\n");
}

// init_main - the second kernel thread used to create user_main kernel threads
static int
init_main(void *arg) {
    cprintf("this initproc, pid = %d, name = \"%s\"\n", current->pid, get_proc_name(current));
    cprintf("To U: \"%s\".\n", (const char *)arg);
    cprintf("To U: \"en.., Bye, Bye. :)\"\n");
    return 0;
}

// proc_init - set up the first kernel thread idleproc "idle" by itself and 
//           - create the second kernel thread init_main
void
proc_init(void) {
    int i;

    list_init(&proc_list);
    for (i = 0; i < HASH_LIST_SIZE; i ++) {
        list_init(hash_list + i);
    }

    if ((idleproc = alloc_proc()) == NULL) {
        panic("cannot alloc idleproc.\n");
    }

    // check the proc structure
    int *context_mem = (int*) kmalloc(sizeof(struct context));
    memset(context_mem, 0, sizeof(struct context));
    int context_init_flag = memcmp(&(idleproc->context), context_mem, sizeof(struct context));

    int *proc_name_mem = (int*) kmalloc(PROC_NAME_LEN);
    memset(proc_name_mem, 0, PROC_NAME_LEN);
    int proc_name_flag = memcmp(&(idleproc->name), proc_name_mem, PROC_NAME_LEN);

    if(idleproc->cr3 == boot_cr3 && idleproc->tf == NULL && !context_init_flag
        && idleproc->state == PROC_UNINIT && idleproc->pid == -1 && idleproc->runs == 0
        && idleproc->kstack == 0 && idleproc->need_resched == 0 && idleproc->parent == NULL
        && idleproc->mm == NULL && idleproc->flags == 0 && !proc_name_flag
    ){
        cprintf("alloc_proc() correct!\n");

    }
    
    idleproc->pid = 0;
    idleproc->state = PROC_RUNNABLE;
    idleproc->kstack = (uintptr_t)bootstack;
    idleproc->need_resched = 1;
    set_proc_name(idleproc, "idle");
    nr_process++;

    current = idleproc;

    int pid = kernel_thread(init_main, "Hello world!!", 0);
    if (pid <= 0) {
        panic("create init_main failed.\n");
    }
    initproc = find_proc(pid);
    set_proc_name(initproc, "init");

    assert(idleproc != NULL && idleproc->pid == 0);
    assert(initproc != NULL && initproc->pid == 1);
}

// cpu_idle - at the end of kern_init, the first kernel thread idleproc will do below works
void
cpu_idle(void) {
    while (1) {
        if (current->need_resched) {
            schedule();
        }
    }
}

